//
// Created by francklinson on 2021/7/4.
//
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

class Solution {
public:
    /**
     * 用bfs或者dfs遍历所有的房间路径 看最后是否所有房间都走到
     * @param rooms
     * @return
     */
    bool canVisitAllRooms(vector<vector<int>> &rooms) {
        vector<bool> reach(rooms.size(), false);
        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            reach[p] = true;
            for (auto &x:rooms[p]) {
                if (not reach[x]) {
                    q.push(x);
                }
            }
        }
        return all_of(reach.begin(), reach.end(), [](bool reached) {
            return reached;
        }) ? true : false;
    }
};
class Solution2 { //dfs
public:
    vector<int> vis;
    int num; // 计数 经过了几间房间

    void dfs(vector<vector<int>>& rooms, int x) {
        vis[x] = true;
        num++;
        for (auto& it : rooms[x]) {
            if (!vis[it]) {
                dfs(rooms, it);
            }
        }
    }

    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        num = 0;
        vis.resize(n);
        dfs(rooms, 0);
        return num == n;
    }
};


int main() {
    vector<vector<int>> rooms{{1, 3},
                              {3, 0, 1},
                              {2},
                              {0}};
    Solution solution;
    cout << solution.canVisitAllRooms(rooms) << endl;
    return 0;
}